/**
 *  Class: Datastructures, CSI 326 Fall 2011
 *  Members: Christopher Nerf, Greg Shevach, Mesfin Solomon, Vidat Muslim
 *  Project: Project 1
 *  Scope: Implement a stack using one of the basic containers we have or will discuss. Example: A vector or list based stack.
 *  	   Implement a queue using one of the basic containers we have or will discuss. Example: A circular array or list based
 *		   queue
 *		   Develop and implement a palindrome checker that uses your stack and/or queue.
 *				 The data to be checked as a palindrome will consist of string characters, possibly containing whitespace and
 *				punctuation.
 *				 A palindrome reads the same forward as backward, ignoring case, whitespace and punctuation.
 *				 The strings to check will be stored in a file, one string per line. The file will contain the string quit to signify
 *				the end of file.
 *				 The strings can be of any length
 *  Version: 0.0 - Initial Pass
 */


//This is a double linked list
// it is updated from the code provided to allow adding elements.



import java.util.Iterator;

public class DoubleList<T> implements ListADT<T>, Iterable<T> {
    protected DoubleNode<T> head;
    protected DoubleNode<T> tail;
    protected int count;

    /**
     * Creates an empty list using the default capacity.
     */
   public DoubleList() {
	tail  = null;
	head  = null;
	count = 0;
    }
   
   public DoubleList(DoubleNode<T> element)
   {
	   tail = element;
	   head = element;
	   //changed to ++count from count++; saved some cycles
	   ++count;
	   
   }

    /**
     * Removes and returns the last element in this list.
     */
    public T removeLast() {
	T result;

	if( isEmpty() )
	    throw new CSI326Exception( "The list is empty" );
      
	result = tail.getElement();
	tail   = tail.getPrevious();
      
	if( tail == null )
	    head = null;
	else
	    tail.setNext( null );

	--count;

	return ( result );
    }

    /**
     * Removes and returns the first element in this list.
     */
    public T removeFirst() {
	if (isEmpty())
	    throw new CSI326Exception ( "The list is empty" );

	T result = head.getElement();
	head = head.getNext();

	if( head == null )
	    tail = null;
	else
	    head.setPrevious( null );
      
	count--;

	return ( result );
    }

    /**
     * Removes and returns the specified element.
     * 
     */
    public T remove (T element) {
	T result;
	DoubleNode<T> nodeptr = find( element );

	if( nodeptr == null )
	    throw new CSI326Exception ( "Element not found" );

	result = nodeptr.getElement();

	/** check to see if head or tail */
	if( nodeptr == head )
	    result = this.removeFirst();
	else if( nodeptr == tail )
	    result = this.removeLast();
	else
	    {
		nodeptr.getNext().setPrevious( nodeptr.getPrevious() );
             	nodeptr.getPrevious().setNext( nodeptr.getNext() );
		count--;
	    }

	return ( result );
    }

    /**
     * Returns a reference to the element at the head of this list.
     * The element is not removed from the list.
     */
    public T first() {
	if( isEmpty() )
	    throw new CSI326Exception ( "The list is empty" );

	return ( head.getElement() );
    }

    /**
     * Returns a reference to the element at the tail of this list.
     * The element is not removed from the list.
     */
    public T last() {
	if( isEmpty() )
	    throw new CSI326Exception ( "The list is empty" );

	return ( tail.getElement() );
    }

    /**
     * Returns a reference to the specified element, or null if it 
     * is not found.
     */
    private DoubleNode<T> find( T target ) {
	boolean found = false;
	DoubleNode<T> traverse = head;
	DoubleNode<T> result   = null;

	if( !isEmpty() )
	    while( !found && traverse != null )
		if( target.equals( traverse.getElement() ) )
		    found = true;
		else
		    traverse = traverse.getNext();

	if( found )
	    result = traverse;

	return ( result );
    }

    /**
     * Returns true if this list is empty and false otherwise. 
     */
    public boolean isEmpty() {
	return ( count == 0 );
    }

    /**
     * Returns the number of elements currently in this list.
     */
    public int size() {
	return ( count );
    }
    /**
     * Add an element to from of list the List
     */
    public void addElementToFront(T element)
    {
    	DoubleNode<T> temp = new DoubleNode<T>(element);
    	//Null pointer exception, need to add test if head is null
	//if it is null, then it's empty, set head and tail both equal to temp.
    	if(head == null)
    	{
    		head = temp;
    		tail = temp;
    	}
    	else
    	{
    		//set pointer in head to temp
    		//set pointer to next in temp to head
    		//set *head = temp
    		head.setPrevious(temp);
    		temp.setNext(head);
    		head = temp;
    	}
    	++count;
    }
    
    /**
     * Add element to end
     */
    
    public void addElementToEnd(T element)
    {
    	if(head == null)
    	{
		//if the list is empty, set it as the head element.
    		this.addElementToFront(element);
    	}
    	else
    	{
		//holds the temporary location of the new node
		//sets the tail as the location of temp
		//set's temps *ptrPrevious to tail.
		//sets *ptrTail to temp
    		DoubleNode<T> temp = new DoubleNode<T>(element);
    		tail.setNext(temp);
    		temp.setPrevious(tail);
    		tail = temp;
    		++count;
    	}
    }   
    
    
    /**
     * Returns an iterator for the elements currently in this list.
     */
    public Iterator<T> iterator() {
	return ( new DoubleIterator<T>( head, count ) );
    }

    /**
     * Returns a string representation of this list. 
     *
     * @return  a string representation of this list
     */
    public String toString() {
	String result = "";
	DoubleNode<T> traverse = head;

	while( traverse != null )
	    { 
		result += traverse.toString() + " ";
		traverse = traverse.getNext();
	    }
	return ( result );
    }
}